import math
from collections import Counter


# 计算两个点之间的欧氏距离
def euclidean_distance(x1, x2):
    return math.sqrt(sum((x1[i] - x2[i]) ** 2 for i in range(len(x1))))


# KNN算法
def knn_classify(train_data, test_point, k):
    # train_data 是一个包含样本的列表，每个样本为 (特征向量, 类别)
    # test_point 是待分类的点，k 是最近邻的数量

    # 计算测试点与每个训练样本的距离
    distances = []
    for features, label in train_data:
        distance = euclidean_distance(features, test_point)
        distances.append((distance, label))

    # 按距离排序，选择k个最近邻
    distances.sort(key=lambda x: x[0])
    nearest_neighbors = distances[:k]

    # 从k个邻居中投票选择类别
    labels = [label for _, label in nearest_neighbors]
    most_common_label = Counter(labels).most_common(1)[0][0]

    return most_common_label


# 示例数据 (特征, 类别)
train_data = [
    ([1.0, 2.0], 'A'),
    ([1.5, 1.8], 'A'),
    ([5.0, 8.0], 'B'),
    ([8.0, 8.0], 'B'),
    ([1.0, 0.6], 'A'),
    ([9.0, 11.0], 'B'),
    ([8.0, 2.0], 'A'),
    ([10.0, 2.0], 'B'),
    ([9.0, 3.0], 'A')
]

# 测试数据点
test_point = [7.0, 3.0]

# 选择k=3
k = 3
predicted_label = knn_classify(train_data, test_point, k)

print(f"测试点 {test_point} 的预测标签为: {predicted_label}")
